package leetcode.editor.cn.dsa06_skiplist;
//不使用任何库函数，设计一个跳表

import java.util.Random;

public class DesignSkiplist1206_3 {
//leetcode submit region begin(Prohibit modification and deletion)
class Skiplist {
    final int HEAD_VALUE = -1; // 链表头节点的值
    final Node HEAD = new Node(HEAD_VALUE);
    Node head; // 最左上角的头节点，所有操作的开始位置
    int levels; // 当前层级，即 head 节点所在的最高层数
    int length; // 跳表长度，即原链表节点个数

    public Skiplist() {
        head = HEAD;
        levels = 1;
        length = 1;
    }

    class Node {
        int val;
        Node right, down;
        Node (int val) {
            this(val, null, null);
        }
        Node (int val, Node right, Node down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }

    /**
     * 从 head 开始，从左到右、从上到下依次查找
     * 1.小于，往右
     * 2.相同，则返回
     * 3.链表结尾，或大于，往下
     * @param target
     * @return
     */
    public boolean search(int target) {
        return get(target) != null;
    }

    /**
     * 插入节点。将节点插入到原链表中正确的排序位置
     * 1.定位插入位置：原链表中 >= num 的最小节点前
     * 2.插入新节点
     * 3.根据扔硬币决定（是否）生成索引
     * @param num
     */
    public void add(int num) {
        // 1.定位插入位置：原链表中 >= num 的最小节点前
        Node node = head;
        // 节点向下，可能是生成索引的位置，使用数组记录这些节点
        Node[] nodes = new Node[levels];
        int i = 0;
        while (node != null) { // node==null 时，到达原链表
            // 在同一层级上向右查找，直到链表结尾，或者找到
            while (node.right != null && node.right.val < num) {
                node = node.right;
            }
            // 原链表也会被记录在内，因此去除原判断
            nodes[i++] = node;
            // 继续查找下一层的位置
            node = node.down;
        }
        // 2.插入新节点
        node = nodes[--i]; // nodes中最后一个元素
        Node newNode = new Node(num, node.right, null);
        node.right = newNode;
        length++; // 每添加一个节点，长度加 1
        // 3.根据扔硬币决定（是否）生成索引
        addIndicesByCoinFlip(newNode, nodes, i); // i 的值代表索引层数，不包含原链表
    }

    /**
     *  抛硬币的方式决定是否给新节点建立索引
     *  索引层级可能超出现有跳表的层数，再抛一次决定是否生成索引
     *  1.抛硬币，在现有跳表层数范围内建立索引
     *  2.抛硬币，决定是否建立一层超出跳表层数的索引层
     * @param target 新节点
     * @param nodes 可能在这些节点后添加新索引节点
     * @param indices 当前索引层数
     */
    private void addIndicesByCoinFlip(Node target, Node[] nodes, int indices) {
        Node downNode = target;
        // 抛硬币决定是否生成索引
        Random random = new Random();
        int coin = random.nextInt(2); // 0 or 1, 50% 概率
        while (coin == 1 && levels < (length >> 6)) { // 右移6位
            if (indices > 0) { // 在现有跳表层数范围内建立索引
                Node prev = nodes[--indices]; // 倒序取数据，跳过原链表
                // 创建索引节点
                Node newIndex = new Node(target.val, prev.right, downNode);
                prev.right = newIndex;
                downNode = newIndex;
                coin = random.nextInt(2);
            } else { // 新建一个索引层级
                // 新建索引节点和 head 节点
                Node newNode = new Node(target.val, null, downNode);
                Node newHead = new Node(HEAD_VALUE, newNode, head);
                head = newHead; // head 指针上移
                levels++; //  跳表层数加 1
            }
        }
    }

    /**
     * 遍历跳表，查找与给定值相同的节点，删除每一层
     * 1.获取该指定数据节点的前一个节点
     * 2.与当前层链表断开
     * 3.下移，删除每一层
     * @param num
     * @return
     */
    public boolean erase(int num) {
        boolean exists = false;
        Node node = get(num);
        while (node != null) {
            Node right = node.right; // 要删除的节点
            // 删除节点
            node.right = right.right;
            right.right = null;
            exists = true;
            // 删除下一层的节点，从node.down开始查找
            node = get(num, node.down);
        }
        if (exists) {
            length--; // 每删除一个节点，长度减1
        }
        return exists;
    }

    private Node get(int target) {
        return get(target, head);
    }

    private Node get(int target, Node from) {
        Node node = from;
        while (node != null) {
            // 1.在同一层级上向右查找，直到链表的结尾
            while (node.right != null && node.right.val < target) {
                node = node.right;
            }
            // 2.若找到，返回true
            Node right = node.right; // 注意right才是要查找的节点
            if (right != null && right.val == target) {
                return node; // 返回要查找的节点的前一个
            }
            // 3.若右侧数据较大，向下一层
            node = node.down;
        }
        return null;
    }
}
/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist obj = new Skiplist();
 * boolean param_1 = obj.search(target);
 * obj.add(num);
 * boolean param_3 = obj.erase(num);
 */
//leetcode submit region end(Prohibit modification and deletion)
}